/*
题目：从根到叶的二进制之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

    例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。
https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
 */
class SumRootToLeaf {
    //优化版
    int ret = 0;//记录答案

    public int sumRootToLeaf(TreeNode root) {
        //val值记录到目前为止的二进制数
        return pathSum(root, 0);//刚开始的值为0
    }

    private int pathSum(TreeNode root, int val) {
        if (root == null)   return 0;
        val = (val << 1) | root.val;
        if (root.left == null && root.right == null) {
            ret += val;
            val >>= 1;//把叶子节点的值撤销
            return ret;
        }
        pathSum(root.left, val);
        pathSum(root.right, val);
        val >>= 1;
        return ret;
    }
}
